{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Tag Validator"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isValid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #标签验证器"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个表示代码片段的字符串，你需要实现一个验证器来解析这段代码，并返回它是否合法。合法的代码片段需要遵守以下的所有规则：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>代码必须被<strong>合法的闭合标签</strong>包围。否则，代码是无效的。</li>\n",
    "\t<li><strong>闭合标签</strong>（不一定合法）要严格符合格式：<code>&lt;TAG_NAME&gt;TAG_CONTENT&lt;/TAG_NAME&gt;</code>。其中，<code>&lt;TAG_NAME&gt;</code>是起始标签，<code>&lt;/TAG_NAME&gt;</code>是结束标签。起始和结束标签中的 TAG_NAME 应当相同。当且仅当&nbsp;TAG_NAME 和 TAG_CONTENT 都是合法的，闭合标签才是<strong>合法的</strong>。</li>\n",
    "\t<li><strong>合法的</strong>&nbsp;<code>TAG_NAME</code>&nbsp;仅含有<strong>大写字母</strong>，长度在范围 [1,9] 之间。否则，该&nbsp;<code>TAG_NAME</code>&nbsp;是<strong>不合法的</strong>。</li>\n",
    "\t<li><strong>合法的</strong>&nbsp;<code>TAG_CONTENT</code>&nbsp;可以包含其他<strong>合法的闭合标签</strong>，<strong>cdata</strong>&nbsp;（请参考规则7）和任意字符（注意参考规则1）<strong>除了</strong>不匹配的<code>&lt;</code>、不匹配的起始和结束标签、不匹配的或带有不合法 TAG_NAME 的闭合标签。否则，<code>TAG_CONTENT</code>&nbsp;是<strong>不合法的</strong>。</li>\n",
    "\t<li>一个起始标签，如果没有具有相同&nbsp;TAG_NAME 的结束标签与之匹配，是不合法的。反之亦然。不过，你也需要考虑标签嵌套的问题。</li>\n",
    "\t<li>一个<code>&lt;</code>，如果你找不到一个后续的<code>&gt;</code>与之匹配，是不合法的。并且当你找到一个<code>&lt;</code>或<code>&lt;/</code>时，所有直到下一个<code>&gt;</code>的前的字符，都应当被解析为&nbsp;TAG_NAME（不一定合法）。</li>\n",
    "\t<li>cdata 有如下格式：<code>&lt;![CDATA[CDATA_CONTENT]]&gt;</code>。<code>CDATA_CONTENT</code>&nbsp;的范围被定义成&nbsp;<code>&lt;![CDATA[</code>&nbsp;和<strong>后续的第一个</strong>&nbsp;<code>]]&gt;</code>之间的字符。</li>\n",
    "\t<li><code>CDATA_CONTENT</code>&nbsp;可以包含<strong>任意字符</strong>。cdata 的功能是阻止验证器解析<code>CDATA_CONTENT</code>，所以即使其中有一些字符可以被解析为标签（无论合法还是不合法），也应该将它们视为<strong>常规字符</strong>。</li>\n",
    "</ol>\n",
    "\n",
    "<p><strong>合法代码的例子:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> &quot;&lt;DIV&gt;This is the first line &lt;![CDATA[&lt;div&gt;]]&gt;&lt;/DIV&gt;&quot;\n",
    "\n",
    "<strong>输出:</strong> True\n",
    "\n",
    "<strong>解释:</strong> \n",
    "\n",
    "代码被包含在了闭合的标签内： &lt;DIV&gt; 和 &lt;/DIV&gt; 。\n",
    "\n",
    "TAG_NAME 是合法的，TAG_CONTENT 包含了一些字符和 cdata 。 \n",
    "\n",
    "即使 CDATA_CONTENT 含有不匹配的起始标签和不合法的 TAG_NAME，它应该被视为普通的文本，而不是标签。\n",
    "\n",
    "所以 TAG_CONTENT 是合法的，因此代码是合法的。最终返回True。\n",
    "\n",
    "\n",
    "<strong>输入:</strong> &quot;&lt;DIV&gt;&gt;&gt;  ![cdata[]] &lt;![CDATA[&lt;div&gt;]&gt;]]&gt;]]&gt;&gt;]&lt;/DIV&gt;&quot;\n",
    "\n",
    "<strong>输出:</strong> True\n",
    "\n",
    "<strong>解释:</strong>\n",
    "\n",
    "我们首先将代码分割为： start_tag|tag_content|end_tag 。\n",
    "\n",
    "start_tag -&gt; <strong>&quot;&lt;DIV&gt;&quot;</strong>\n",
    "\n",
    "end_tag -&gt; <strong>&quot;&lt;/DIV&gt;&quot;</strong>\n",
    "\n",
    "tag_content 也可被分割为： text1|cdata|text2 。\n",
    "\n",
    "text1 -&gt; <strong>&quot;&gt;&gt;  ![cdata[]] &quot;</strong>\n",
    "\n",
    "cdata -&gt; <strong>&quot;&lt;![CDATA[&lt;div&gt;]&gt;]]&gt;&quot;</strong> ，其中 CDATA_CONTENT 为 <strong>&quot;&lt;div&gt;]&gt;&quot;</strong>\n",
    "\n",
    "text2 -&gt; <strong>&quot;]]&gt;&gt;]&quot;</strong>\n",
    "\n",
    "\n",
    "start_tag <strong>不</strong>是 <strong>&quot;&lt;DIV&gt;&gt;&gt;&quot;</strong> 的原因参照规则 6 。\n",
    "cdata <strong>不</strong>是 <strong>&quot;&lt;![CDATA[&lt;div&gt;]&gt;]]&gt;]]&gt;&quot;</strong> 的原因参照规则 7 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>不合法代码的例子:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> &quot;&lt;A&gt;  &lt;B&gt; &lt;/A&gt;   &lt;/B&gt;&quot;\n",
    "<strong>输出:</strong> False\n",
    "<strong>解释:</strong> 不合法。如果 &quot;&lt;A&gt;&quot; 是闭合的，那么 &quot;&lt;B&gt;&quot; 一定是不匹配的，反之亦然。\n",
    "\n",
    "<strong>输入:</strong> &quot;&lt;DIV&gt;  div tag is not closed  &lt;DIV&gt;&quot;\n",
    "<strong>输出:</strong> False\n",
    "\n",
    "<strong>输入:</strong> &quot;&lt;DIV&gt;  unmatched &lt;  &lt;/DIV&gt;&quot;\n",
    "<strong>输出:</strong> False\n",
    "\n",
    "<strong>输入:</strong> &quot;&lt;DIV&gt; closed tags with invalid tag name  &lt;b&gt;123&lt;/b&gt; &lt;/DIV&gt;&quot;\n",
    "<strong>输出:</strong> False\n",
    "\n",
    "<strong>输入:</strong> &quot;&lt;DIV&gt; unmatched tags with invalid tag name  &lt;/1234567890&gt; and &lt;CDATA[[]]&gt;  &lt;/DIV&gt;&quot;\n",
    "<strong>输出:</strong> False\n",
    "\n",
    "<strong>输入:</strong> &quot;&lt;DIV&gt;  unmatched start tag &lt;B&gt;  and unmatched end tag &lt;/C&gt;  &lt;/DIV&gt;&quot;\n",
    "<strong>输出:</strong> False\n",
    "</pre>\n",
    "\n",
    "<p><strong>注意:</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li>为简明起见，你可以假设输入的代码（包括提到的<strong>任意字符</strong>）只包含<code>数字</code>, <font color=\"#c7254e\" face=\"Menlo, Monaco, Consolas, Courier New, monospace\"><span style=\"background-color:#f9f2f4; font-size:12.6px\">字母</span></font>, <code>&#39;&lt;&#39;</code>,<code>&#39;&gt;&#39;</code>,<code>&#39;/&#39;</code>,<code>&#39;!&#39;</code>,<code>&#39;[&#39;</code>,<code>&#39;]&#39;</code>和<code>&#39; &#39;</code>。</li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [tag-validator](https://leetcode.cn/problems/tag-validator/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [tag-validator](https://leetcode.cn/problems/tag-validator/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"<DIV>This is the first line <![CDATA[<div>]]></DIV>\"', '\"<DIV>>>  ![cdata[]] <![CDATA[<div>]>]]>]]>>]</DIV>\"', '\"<A>  <B> </A>   </B>\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "CDATA_CONTENT_PATTERN = r'<!\\[CDATA\\[.*?\\]\\]>'\n",
    "TAG_CONTENT_PATTERN = r'<([A-Z]{1,9})>[^<]*</\\1>'\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, code: str) -> bool:\n",
    "        code = re.sub(CDATA_CONTENT_PATTERN, \"#\", code)\n",
    "        for _ in range(code.count('</')):\n",
    "            code = re.sub(TAG_CONTENT_PATTERN, \"#\", code)\n",
    "        return code == \"#\"\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, code: str) -> bool:\n",
    "        code=re.sub(r'<!\\[CDATA\\[(.)*?\\]\\]>','x',code) # 非贪婪风格\n",
    "        prev=\"\"\n",
    "        while code!=prev:\n",
    "            prev=code\n",
    "            code=re.sub(r'<([A-Z]{1,9})>[^<]*</\\1>','y',code)\n",
    "        return code=='y'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "CDATA_CONTENT_PATTERN = r'<!\\[CDATA\\[.*?\\]\\]>'\n",
    "TAG_CONTENT_PATTERN = r'<([A-Z]{1,9})>[^<]*</\\1>'\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, code: str) -> bool:\n",
    "        code = re.sub(CDATA_CONTENT_PATTERN, \"#\", code)\n",
    "        for _ in range(code.count('</')):\n",
    "            code = re.sub(TAG_CONTENT_PATTERN, \"#\", code)\n",
    "        return code == \"#\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, code: str) -> bool:\n",
    "        code=re.sub(r'<!\\[CDATA\\[(.)*?\\]\\]>','x',code) # 非贪婪风格\n",
    "        print(code)\n",
    "        prev=\"\"\n",
    "        while code!=prev:\n",
    "            prev=code\n",
    "            code=re.sub(r'<([A-Z]{1,9})>[^<]*</\\1>','y',code)\n",
    "            print(code)\n",
    "        return code=='y'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self,code):\n",
    "        self.s=code\n",
    "        if self.s[0]!=\"<\" or self.s[-1]!=\">\":\n",
    "            return False\n",
    "        self.skipchar()\n",
    "        name=self.expecttagname()\n",
    "        #print(name)\n",
    "        if not name:\n",
    "            return False\n",
    "        # print(name)\n",
    "        return self.completetag(name) and self.s==''\n",
    "    def expecttagname(self):\n",
    "        st=''\n",
    "        for _ in range(9):\n",
    "            if not self.s[0].isupper():\n",
    "                break\n",
    "            st+=self.s[0]\n",
    "            self.skipchar()\n",
    "            if len(self.s)>0 and self.s[0]==\">\":\n",
    "                #s+=self.s[0]\n",
    "                self.skipchar()\n",
    "                #print(s)\n",
    "                return st\n",
    "\n",
    "        return ''\n",
    "    def expectcdata(self):\n",
    "        if self.s[:8]!='![CDATA[':\n",
    "            return False\n",
    "        self.s=self.s[8:]\n",
    "        while len(self.s)>=3:\n",
    "            if  self.s[:3]==']]>':\n",
    "                self.skipchar()\n",
    "                self.skipchar()\n",
    "                self.skipchar()\n",
    "                return True\n",
    "            self.skipchar()\n",
    "        return False\n",
    "\n",
    "    def skipchar(self):\n",
    "        self.s=self.s[1:]\n",
    "    def skipcon(self):\n",
    "        while self.s and self.s[0]!='<':\n",
    "            self.skipchar()\n",
    "    def completetag(self,name):\n",
    "        #n=len(name)\n",
    "        self.skipcon()\n",
    "        if not self.s:\n",
    "            return False\n",
    "        assert self.s[0]=='<'\n",
    "        self.skipchar()\n",
    "        if self.s[0]=='!':\n",
    "            #CDATA\n",
    "            #print(self.s)\n",
    "\n",
    "            if not self.expectcdata():\n",
    "                return False\n",
    "            return self.completetag(name)\n",
    "        if self.s[0]=='/':\n",
    "        #NAME\n",
    "            self.skipchar()\n",
    "            s1=self.expecttagname()\n",
    "            return s1==name\n",
    "        # elif self.s[1]!='/':\n",
    "        #     return False\n",
    "        tag=self.expecttagname()\n",
    "\n",
    "        if not tag:\n",
    "            return False\n",
    "        if not self.completetag(tag):\n",
    "            return False\n",
    "        return self.completetag(name)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, code: str) -> bool:\n",
    "        code = re.sub(r'<!\\[CDATA\\[.*?\\]\\]>|t', '-', code)\n",
    "        prev = None\n",
    "        while code != prev:\n",
    "            prev = code\n",
    "            code = re.sub(r'<([A-Z]{1,9})>[^<]*</\\1>', 't', code)\n",
    "        return code == 't'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, code: str) -> bool:\n",
    "        code = re.sub(r'<!\\[CDATA\\[.*?\\]\\]>|t', '-', code)\n",
    "        prev = None\n",
    "        while code != prev:\n",
    "            prev = code\n",
    "            code = re.sub(r'<([A-Z]{1,9})>[^<]*</\\1>', 't', code)\n",
    "        return code == 't'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, code: str) -> bool:\n",
    "        '''\n",
    "        正则表达式的思路挺好，但是记不住\n",
    "        照着官方题解，做一遍堆栈思路\n",
    "        '''\n",
    "        # 开始标签则入栈，结束标签则出栈\n",
    "        n = len(code)\n",
    "        tags = list()\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if code[i] == '<':\n",
    "                if i == n - 1:\n",
    "                    return False\n",
    "                if code[i+1] == '/':\n",
    "                    j = code.find('>', i)\n",
    "                    if j == -1:\n",
    "                        return False\n",
    "                    tagname = code[i+2: j]\n",
    "                    if not tags or tags[-1] != tagname:\n",
    "                        return False\n",
    "                    tags.pop()\n",
    "                    i = j + 1\n",
    "                    # 没有其他开始标签了，但是结束标签后面还有字符\n",
    "                    if not tags and i != n:\n",
    "                        return False\n",
    "                elif code[i+1] == '!':\n",
    "                    if not tags:\n",
    "                        return False\n",
    "                    cdata = code[i+2:i+9]\n",
    "                    if cdata != \"[CDATA[\":\n",
    "                        return False\n",
    "                    j = code.find(\"]]>\", i)\n",
    "                    if j == -1:\n",
    "                        return False\n",
    "                    i = j + 3\n",
    "                else:\n",
    "                    j = code.find('>', i)\n",
    "                    if j == -1:\n",
    "                        return False\n",
    "                    tagname = code[i+1: j]\n",
    "                    if not 1 <= len(tagname) <= 9 or not all(ch.isupper() for ch in tagname):\n",
    "                        return False\n",
    "                    tags.append(tagname)\n",
    "                    i = j + 1\n",
    "            else:\n",
    "                if not tags:\n",
    "                    return False\n",
    "                i += 1\n",
    "        return not tags"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, code: str) -> bool:\n",
    "        n = len(code)\n",
    "        tags = list()\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if code[i]==\"<\":\n",
    "                if i==n-1:\n",
    "                    return False\n",
    "                if code[i+1]==\"/\":\n",
    "                    j=code.find(\">\",i)\n",
    "                    if j==-1:\n",
    "                        return False\n",
    "                    tagname=code[i+2:j]\n",
    "                    if not tags or tags[-1] != tagname:\n",
    "                        return False\n",
    "                    tags.pop()\n",
    "                    i=j+1\n",
    "                    if not tags and i != n:\n",
    "                        return False\n",
    "                elif code[i + 1] == \"!\":\n",
    "                    if not tags:\n",
    "                        return False\n",
    "                    cdata = code[i+2:i+9]\n",
    "                    if cdata != \"[CDATA[\":\n",
    "                        return False\n",
    "                    j = code.find(\"]]>\", i)\n",
    "                    if j == -1:\n",
    "                        return False\n",
    "                    i=j+3\n",
    "                else:\n",
    "                    j = code.find(\">\", i)\n",
    "                    if j == -1:\n",
    "                        return False\n",
    "                    tagname = code[i+1:j]\n",
    "                    if not 1 <= len(tagname) <= 9 or not all(ch.isupper() for ch in tagname):\n",
    "                        return False\n",
    "                    tags.append(tagname)\n",
    "                    i = j + 1\n",
    "            else:\n",
    "                if not tags:\n",
    "                    return False\n",
    "                i += 1\n",
    "        return not tags\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, code: str) -> bool:\n",
    "        n = len(code)\n",
    "        tags = list()\n",
    "\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if code[i] == \"<\":\n",
    "                if i == n - 1:\n",
    "                    return False\n",
    "                if code[i + 1] == \"/\":\n",
    "                    j = code.find(\">\", i)\n",
    "                    if j == -1:\n",
    "                        return False\n",
    "                    tagname = code[i+2:j]\n",
    "                    if not tags or tags[-1] != tagname:\n",
    "                        return False\n",
    "                    tags.pop()\n",
    "                    i = j + 1\n",
    "                    if not tags and i != n:\n",
    "                        return False\n",
    "                elif code[i + 1] == \"!\":\n",
    "                    if not tags:\n",
    "                        return False\n",
    "                    cdata = code[i+2:i+9]\n",
    "                    if cdata != \"[CDATA[\":\n",
    "                        return False\n",
    "                    j = code.find(\"]]>\", i)\n",
    "                    if j == -1:\n",
    "                        return False\n",
    "                    i = j + 3\n",
    "                else:\n",
    "                    j = code.find(\">\", i)\n",
    "                    if j == -1:\n",
    "                        return False\n",
    "                    tagname = code[i+1:j]\n",
    "                    if not 1 <= len(tagname) <= 9 or not all(ch.isupper() for ch in tagname):\n",
    "                        return False\n",
    "                    tags.append(tagname)\n",
    "                    i = j + 1\n",
    "            else:\n",
    "                if not tags:\n",
    "                    return False\n",
    "                i += 1\n",
    "        \n",
    "        return not tags"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self,code):\n",
    "        self.s=code\n",
    "        if self.s[0]!=\"<\" or self.s[-1]!=\">\":\n",
    "            return False\n",
    "        self.skipchar()\n",
    "        name=self.expecttagname()\n",
    "        #print(name)\n",
    "        if not name:\n",
    "            return False\n",
    "        # print(name)\n",
    "        return self.completetag(name) and self.s==''\n",
    "    def expecttagname(self):\n",
    "        st=''\n",
    "        for _ in range(10):\n",
    "            if not self.s[0].isupper() and self.s[0]!='/':\n",
    "                break\n",
    "            st+=self.s[0]\n",
    "            self.skipchar()\n",
    "            if len(self.s)>0 and self.s[0]==\">\":\n",
    "                #s+=self.s[0]\n",
    "                self.skipchar()\n",
    "                #print(s)\n",
    "                return st\n",
    "\n",
    "        return ''\n",
    "    def expectcdata(self):\n",
    "        if self.s[:8]!='![CDATA[':\n",
    "            return False\n",
    "        self.s=self.s[8:]\n",
    "        while len(self.s)>=3:\n",
    "            if  self.s[:3]==']]>':\n",
    "                self.skipchar()\n",
    "                self.skipchar()\n",
    "                self.skipchar()\n",
    "                return True\n",
    "            self.skipchar()\n",
    "        return False\n",
    "\n",
    "    def skipchar(self):\n",
    "        self.s=self.s[1:]\n",
    "    def skipcon(self):\n",
    "        while self.s and self.s[0]!='<':\n",
    "            self.skipchar()\n",
    "    def completetag(self,name):\n",
    "        #n=len(name)\n",
    "        self.skipcon()\n",
    "        if not self.s:\n",
    "            return False\n",
    "        assert self.s[0]=='<'\n",
    "        self.skipchar()\n",
    "        if self.s[0]=='!':\n",
    "            #CDATA\n",
    "            #print(self.s)\n",
    "\n",
    "            if not self.expectcdata():\n",
    "                return False\n",
    "            return self.completetag(name)\n",
    "        if self.s[0]=='/':\n",
    "\n",
    "        #NAME\n",
    "            s1=self.expecttagname()\n",
    "            return s1[1:]==name\n",
    "        # elif self.s[1]!='/':\n",
    "        #     return False\n",
    "        tag=self.expecttagname()\n",
    "\n",
    "        if not tag:\n",
    "            return False\n",
    "        if not self.completetag(tag):\n",
    "            return False\n",
    "        return self.completetag(name)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, code: str) -> bool:\n",
    "        self.code = code\n",
    "        if self.code[0] != '<':\n",
    "            return False\n",
    "        self.skip_one_char()\n",
    "        savt = self.expect_tag_name()\n",
    "        if not savt:\n",
    "            return False\n",
    "        return self.complete_tag(savt) and self.code == ''\n",
    "\n",
    "    def expect_tag_name(self):\n",
    "        if self.is_empty(): return ''\n",
    "        s = ''\n",
    "        for _ in range(9):\n",
    "            if self.is_empty() or self.code[0] not in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ':\n",
    "                break\n",
    "            s += self.code[0]\n",
    "            self.skip_one_char()\n",
    "        if self.is_empty(): return ''\n",
    "        if len(s) > 0 and self.code[0] == '>':\n",
    "            self.skip_one_char()\n",
    "            return s\n",
    "        return ''\n",
    "\n",
    "    def skip_one_char(self):\n",
    "        self.code = self.code[1:]\n",
    "    def complete_tag(self,savt):\n",
    "        while self.code and self.code[0] != '<':\n",
    "            self.skip_one_char()\n",
    "        if self.is_empty(): return False\n",
    "        self.skip_one_char()\n",
    "        if self.code[0] == '!':\n",
    "            if not self.expect_cdata():\n",
    "                return False\n",
    "            return self.complete_tag(savt)\n",
    "        if self.code[0] == '/':\n",
    "            self.skip_one_char()\n",
    "            return self.expect_tag_name() == savt\n",
    "        tag = self.expect_tag_name()\n",
    "        if not tag:\n",
    "            return False\n",
    "        if not self.complete_tag(tag):\n",
    "            return False\n",
    "        return self.complete_tag(savt)\n",
    "    \n",
    "    def is_empty(self):\n",
    "        return self.code == ''\n",
    "\n",
    "    def expect_cdata(self):\n",
    "        if self.code[:8] != '![CDATA[':\n",
    "            return False\n",
    "        self.code = self.code[8:]\n",
    "        while len(self.code) >= 3:\n",
    "            if self.code[:3] == ']]>':\n",
    "                self.code = self.code[3:]\n",
    "                return True\n",
    "            self.skip_one_char()\n",
    "        return False\n",
    "    #     self.code = code\n",
    "    #     if self.code[0] != \"<\":\n",
    "    #         return False\n",
    "    #     b = self.Tag_Name()\n",
    "    #     if b == -1:\n",
    "    #         return False\n",
    "    #     self.code = self.code[b:len(self.code)-b-1]\n",
    "    #     return self.complete()\n",
    "    # def Tag_Name(self):\n",
    "    #     a = 0\n",
    "    #     for i in range(1, len(self.code)):\n",
    "    #         if self.code[i] == \">\":\n",
    "    #             a = i\n",
    "    #             break\n",
    "    #     if a == 0 or a > 10:\n",
    "    #         return -1\n",
    "    #     if self.code[1] == \"/\":\n",
    "    #         return -1\n",
    "    #     if self.code[-a - 1] != \"/\":\n",
    "    #         return -1\n",
    "    #     if not self.code[1:a].isupper():\n",
    "    #         return -1\n",
    "    #     if self.code[1:a] != self.code[-a:-1]:\n",
    "    #         return -1\n",
    "    #     return a+1\n",
    "    # def is_empty(self):\n",
    "    #     return self.code == ''\n",
    "    # def complete(self):\n",
    "    #     while self.is_empty() and self.code[0] != \"<\":\n",
    "    #         self.code = self.code[1:]\n",
    "    #     b = self.Tag_Name()\n",
    "    #     if b != -1:\n",
    "    #         self.code = self.code[b:self.n-b-1]\n",
    "    #         return self.complete()\n",
    "    #     else:\n",
    "    #         self.code = self.code[1:]\n",
    "    #         if self.code[0] == \"!\":\n",
    "    #             if not self.expect_cdata():\n",
    "    #                 return False\n",
    "    #             return self.complete()\n",
    "    #     return True\n",
    "\n",
    "    # def expect_cdata(self):\n",
    "    #     if self.code[:8] != '![CDATA[':\n",
    "    #         return False\n",
    "    #     self.code = self.code[8:]\n",
    "    #     while len(self.code) >= 3:\n",
    "    #         if self.code[:3] == ']]>':\n",
    "    #             self.code = self.code[3:]\n",
    "    #             return True\n",
    "    #         self.code = self.code[1:]\n",
    "    #     return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, code: str) -> bool:\n",
    "        import re\n",
    "        code = re.sub(r'<!\\[CDATA\\[.*?\\]\\]>|t', '-', code)\n",
    "        prev = None\n",
    "        while code != prev:\n",
    "            prev = code\n",
    "            code = re.sub(r'<([A-Z]{1,9})>[^<]*</\\1>', 't', code)\n",
    "        return code == 't'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, code: str) -> bool:\n",
    "        def isUppercase(ch):\n",
    "            return ord(ch) >= ord('A') and ord(ch) <= ord('Z')\n",
    "        def getTagName(s):\n",
    "            tagName = ''\n",
    "            for i in range(len(s)):\n",
    "                if isUppercase(s[i]):\n",
    "                    tagName = tagName + s[i]\n",
    "                else:\n",
    "                    break\n",
    "            return tagName\n",
    "\n",
    "        ind = 0\n",
    "        stack = []\n",
    "        hasTag = False\n",
    "        if code[0] != '<':\n",
    "            return False\n",
    "        while ind < len(code):\n",
    "            if len(stack) == 0 and hasTag == True:\n",
    "                return False\n",
    "            if code[ind] == '<':\n",
    "                if ind + 1 < len(code) and code[ind+1] != '/' and code[ind+1] != '!':\n",
    "                    ind += 1\n",
    "                    tagName = getTagName(code[ind:])\n",
    "                    if len(tagName) < 1 or len(tagName) > 9 or ind + len(tagName) >= len(code) or code[ind + len(tagName)] != '>':\n",
    "                        return False\n",
    "                    if hasTag == False:\n",
    "                        hasTag = True\n",
    "                    elif hasTag == True and len(stack) == 0:\n",
    "                        return False\n",
    "                    stack.append(tagName)\n",
    "                    ind += len(tagName)\n",
    "                elif ind + 1 < len(code) and code[ind+1] == '/':\n",
    "                    ind += 2\n",
    "                    if ind >= len(code):\n",
    "                        return False\n",
    "                    tagName = getTagName(code[ind:])\n",
    "                    if len(stack) == 0:\n",
    "                        return False\n",
    "                    tagName_ = stack.pop()\n",
    "                    if tagName != tagName_:\n",
    "                        return False\n",
    "                    ind += len(tagName)\n",
    "                    if ind >= len(code) or code[ind] != '>':\n",
    "                        return False\n",
    "                    ind += 1\n",
    "                elif ind + 1 < len(code) and code[ind+1] == '!':\n",
    "                    if hasTag == False:\n",
    "                        return False\n",
    "                    if ind+9 >= len(code) or code[ind:ind+9] != '<![CDATA[':\n",
    "                        return False\n",
    "                    ind += 9\n",
    "                    cdataEnd = False\n",
    "                    while ind < len(code):\n",
    "                        if code[ind] == ']':\n",
    "                            if ind+2 < len(code) and code[ind:ind+3] == ']]>':\n",
    "                                cdataEnd = True\n",
    "                                ind += 3\n",
    "                                break\n",
    "                        ind += 1\n",
    "                    if cdataEnd == False:\n",
    "                        return False\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                ind += 1\n",
    "        if len(stack) != 0 or hasTag == False:\n",
    "            return False\n",
    "        return True\n",
    "                        \n",
    "\n",
    "                                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, code: str) -> bool:\n",
    "        code = re.sub(r'<!\\[CDATA\\[.*?\\]\\]>|t', '-', code)\n",
    "        prev = None\n",
    "        while code != prev:\n",
    "            prev = code\n",
    "            code = re.sub(r'<([A-Z]{1,9})>[^<]*</\\1>', 't', code)\n",
    "        return code == 't'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "CDATA_CONTENT_PATTERN = r'<!\\[CDATA\\[.*?\\]\\]>'\n",
    "TAG_CONTENT_PATTERN = r'<([A-Z]{1,9})>[^<]*</\\1>'\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, code: str) -> bool:\n",
    "        code=re.sub(CDATA_CONTENT_PATTERN,\"#\",code)\n",
    "        for _ in range(code.count('</')):\n",
    "            code=re.sub(TAG_CONTENT_PATTERN,\"#\",code)\n",
    "        return code==\"#\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, code: str) -> bool:\n",
    "        n = len(code)\n",
    "        tags = list()\n",
    "\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if code[i] == \"<\":\n",
    "                if i == n - 1:\n",
    "                    return False\n",
    "                if code[i + 1] == \"/\":\n",
    "                    j = code.find(\">\", i)\n",
    "                    if j == -1:\n",
    "                        return False\n",
    "                    tagname = code[i+2:j]\n",
    "                    if not tags or tags[-1] != tagname:\n",
    "                        return False\n",
    "                    tags.pop()\n",
    "                    i = j + 1\n",
    "                    if not tags and i != n:\n",
    "                        return False\n",
    "                elif code[i + 1] == \"!\":\n",
    "                    if not tags:\n",
    "                        return False\n",
    "                    cdata = code[i+2:i+9]\n",
    "                    if cdata != \"[CDATA[\":\n",
    "                        return False\n",
    "                    j = code.find(\"]]>\", i)\n",
    "                    if j == -1:\n",
    "                        return False\n",
    "                    i = j + 3\n",
    "                else:\n",
    "                    j = code.find(\">\", i)\n",
    "                    if j == -1:\n",
    "                        return False\n",
    "                    tagname = code[i+1:j]\n",
    "                    if not 1 <= len(tagname) <= 9 or not all(ch.isupper() for ch in tagname):\n",
    "                        return False\n",
    "                    tags.append(tagname)\n",
    "                    i = j + 1\n",
    "            else:\n",
    "                if not tags:\n",
    "                    return False\n",
    "                i += 1\n",
    "        \n",
    "        return not tags\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, code: str) -> bool:\n",
    "        stack = []\n",
    "        i = 0\n",
    "\n",
    "        def valid_name(name):\n",
    "            size = len(name)\n",
    "            acode, zcode = ord('A'), ord('Z')\n",
    "            if size < 1 or size > 9:\n",
    "                return False\n",
    "            for char in name:\n",
    "                if ord(char) < acode or ord(char) > zcode:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        while i < len(code):\n",
    "            if i > 0 and not stack:\n",
    "                return False\n",
    "            if code[i:i + 9] == \"<![CDATA[\":\n",
    "                j = i + 9\n",
    "                while j + 2 < len(code):\n",
    "                    if code[j: j + 3] == \"]]>\":\n",
    "                        break\n",
    "                    j += 1\n",
    "                if j + 2 >= len(code): return False\n",
    "                i = j + 3\n",
    "            elif code[i:i + 2] == \"</\":\n",
    "                j = i + 2\n",
    "                while j < len(code) and code[j] != '>':\n",
    "                    j += 1\n",
    "                if j == len(code):\n",
    "                    return False\n",
    "                temptag = code[i + 2: j]\n",
    "                if not valid_name(temptag): return False\n",
    "                if not stack or stack[-1] != temptag: \n",
    "                    return False\n",
    "                else:\n",
    "                    stack.pop()\n",
    "                i = j + 1\n",
    "            elif code[i] == \"<\":\n",
    "                j = i + 1\n",
    "                while j < len(code) and code[j] != '>':\n",
    "                    j += 1\n",
    "                if j == len(code): return False\n",
    "                temptag = code[i + 1: j]\n",
    "                if not valid_name(temptag): return False\n",
    "                stack.append(temptag)\n",
    "                i = j + 1\n",
    "            else:\n",
    "                i += 1\n",
    "        return not stack\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import re\r\n",
    "class Solution:\r\n",
    "\r\n",
    "    def isValid(self, code: str) -> bool:\r\n",
    "        # def check_tag(start:int,end:int):   \r\n",
    "        #     ret=[-1,-1]\r\n",
    "        #     if code[start]!='<' or code[end]!='>':\r\n",
    "        #         return ret\r\n",
    "        #     start_end=-1\r\n",
    "        #     for i in range(start+1,end):\r\n",
    "        #         if code[i].isupper():\r\n",
    "        #             continue\r\n",
    "        #         elif code[start_end]=='>':\r\n",
    "        #             start_end=i\r\n",
    "        #             break\r\n",
    "        #         else:\r\n",
    "        #             return ret\r\n",
    "        #     else:\r\n",
    "        #         return ret\r\n",
    "        #     start_tag_len=start_end-start-1\r\n",
    "        #     if start_tag_len<1 or start_tag_len>9:\r\n",
    "        #         return ret\r\n",
    "            \r\n",
    "        #     end_start=-1\r\n",
    "        #     for i in range(end-1,start,-1):\r\n",
    "        #         if code[i].isupper():\r\n",
    "        #             continue\r\n",
    "        #         elif code[i]=='/' and code[i-1]=='<':\r\n",
    "        #             end_start=i-1\r\n",
    "        #             break\r\n",
    "        #         else:\r\n",
    "        #             return ret\r\n",
    "        #     else:\r\n",
    "        #         return ret\r\n",
    "            \r\n",
    "        #     end_tag_len=end-end_start-2\r\n",
    "        #     if end_tag_len!=start_tag_len or code[start+1:start_end]!=code[end_start+2:end]:\r\n",
    "        #         return ret\r\n",
    "        #     return [start_end+1,end_start-1]\r\n",
    "        \r\n",
    "        # return tag name or ''\r\n",
    "        # start is '<' or '/' \r\n",
    "        def extract_tag(start:int,end:int):\r\n",
    "\r\n",
    "            for i in range(start+1,end+1):\r\n",
    "                if code[i].isupper():\r\n",
    "                    continue\r\n",
    "                elif code[i]=='>':\r\n",
    "                    return code[start+1:i]\r\n",
    "                else:\r\n",
    "                    return ''\r\n",
    "            return ''\r\n",
    "        \r\n",
    "        # code[start]=='<'\r\n",
    "        def check_cdata(start:int,end:int):\r\n",
    "            pattern=r'<!\\[CDATA\\[.*?\\]\\]>'\r\n",
    "            group=re.match(pattern,code[start:end+1])\r\n",
    "            if not group:\r\n",
    "                return -1\r\n",
    "            return group.span()[1]+start\r\n",
    "\r\n",
    "        # def check_content(start,end):\r\n",
    "        #     while start<end and code[start]!='<':\r\n",
    "        #         start+=1\r\n",
    "            \r\n",
    "\r\n",
    "        L=len(code)\r\n",
    "        stack=[]\r\n",
    "        idx=0\r\n",
    "        while idx<L:\r\n",
    "            if code[idx]=='<':\r\n",
    "                if idx+1==L:\r\n",
    "                    return False\r\n",
    "                ch=code[idx+1]\r\n",
    "                if ch=='/':\r\n",
    "                    if not stack:\r\n",
    "                        return False\r\n",
    "                    end_tag=extract_tag(idx+1,L-1)\r\n",
    "                    if not end_tag or len(end_tag)>9 or not stack or stack[-1]!=end_tag:\r\n",
    "                        return False\r\n",
    "                    else:\r\n",
    "                        stack.pop()\r\n",
    "                    idx+=len(end_tag)+3\r\n",
    "                elif ch=='!':\r\n",
    "                    if not stack:\r\n",
    "                        return False\r\n",
    "                    data_end=check_cdata(idx,L-1)\r\n",
    "                    if data_end<0:\r\n",
    "                        return False\r\n",
    "                    idx=data_end\r\n",
    "                else:\r\n",
    "                    if idx>0 and not stack:\r\n",
    "                        return False\r\n",
    "                    start_tag=extract_tag(idx,L-1)\r\n",
    "                    if not start_tag or len(start_tag)>9:\r\n",
    "                        return False\r\n",
    "                    stack.append(start_tag)\r\n",
    "                    idx+=len(start_tag)+2\r\n",
    "            elif not stack:\r\n",
    "                return False\r\n",
    "            else:\r\n",
    "                idx+=1\r\n",
    "\r\n",
    "        return len(stack)==0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replace_cdata(self,code):\n",
    "        cdata_start = code.find('<![CDATA[')\n",
    "        while cdata_start >=0:\n",
    "            cdata_end = code.find(']]>',cdata_start)\n",
    "            if cdata_end < 0:\n",
    "                return code\n",
    "            code = code[:cdata_start] +'*'+ code[cdata_end+3:]\n",
    "            cdata_start = code.find('<![CDATA[')\n",
    "        return code\n",
    "\n",
    "    def check_tag(self,tag):\n",
    "        if len(tag) >9 or len(tag) < 1:\n",
    "            return False\n",
    "        \n",
    "        for c in tag:\n",
    "            if (ord(c) < ord('A')) or (ord(c) > ord('Z')):\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def isValid(self, code: str) -> bool:\n",
    "        code = self.replace_cdata(code)\n",
    "        if len(code) <= 0 or code[0] != '<':\n",
    "            return False\n",
    "        # print (code)\n",
    "        tag_stack = []\n",
    "        start,end = -1,0\n",
    "\n",
    "        for i,c in enumerate(code):\n",
    "            if c == '<':\n",
    "                if start >= 0:\n",
    "                    return False\n",
    "                start = i\n",
    "            if c == '>':\n",
    "                end = i\n",
    "                if start >= 0:\n",
    "                    tag = code[start+1:end]\n",
    "                    is_tag_end = False\n",
    "\n",
    "                    if tag and tag[0] == '/':\n",
    "                        is_tag_end = True\n",
    "                        tag = tag[1:]\n",
    "                    if self.check_tag(tag):\n",
    "                        if is_tag_end:\n",
    "                            if len(tag_stack) < 1:\n",
    "                                return False\n",
    "                            start_tag = tag_stack.pop()\n",
    "                            if start_tag != tag:\n",
    "                                return False\n",
    "                            elif len(tag_stack)==0 and i != len(code) - 1:\n",
    "                                return False\n",
    "                        else:\n",
    "                            tag_stack.append(tag)\n",
    "                    else:\n",
    "                        return False\n",
    "                    start = -1\n",
    "        if start >= 0 or len(tag_stack) > 0:\n",
    "            return False\n",
    "        \n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, code: str) -> bool:\n",
    "        stack = []\n",
    "        i = 0\n",
    "        while i < len(code):\n",
    "            if i > 0 and not stack:\n",
    "                return False\n",
    "            if code[i:i+9] == \"<![CDATA[\":\n",
    "                j = i + 9\n",
    "                while j < len(code) - 2:\n",
    "                    if code[j:j+3] == \"]]>\":\n",
    "                        break\n",
    "                    j += 1\n",
    "                if j >= len(code) - 2:\n",
    "                    return False\n",
    "                i = j + 3\n",
    "            elif code[i:i+2] == \"</\":\n",
    "                j = i + 2\n",
    "                while j < len(code) and code[j] != '>':\n",
    "                    if ord(code[j]) < ord('A') or ord(code[j]) > ord('Z'):\n",
    "                        return False\n",
    "                    j += 1\n",
    "                if j >= len(code) or j == i + 2 or j > i + 11:\n",
    "                    return False\n",
    "                tag = code[i+2:j]\n",
    "                if not stack or stack[-1] != tag or not tag.isupper():\n",
    "                    return False\n",
    "                stack.pop()\n",
    "                i = j + 1\n",
    "            elif code[i] == '<':\n",
    "                j = i + 1\n",
    "                while j < len(code) and code[j] != '>':\n",
    "                    if ord(code[j]) < ord('A') or ord(code[j]) > ord('Z'):\n",
    "                        return False\n",
    "                    j += 1\n",
    "                if j >= len(code) or j == i + 1 or j > i + 10:\n",
    "                    return False\n",
    "                tag = code[i+1:j]\n",
    "                if not tag.isupper():\n",
    "                    return False\n",
    "                stack.append(tag)\n",
    "                i = j + 1\n",
    "            else:\n",
    "                i += 1\n",
    "        return not stack\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, code: str) -> bool:\n",
    "        stack = []\n",
    "        i = 0\n",
    "        valid = False\n",
    "        while i < len(code):\n",
    "            if i > 0 and not stack:\n",
    "                return False\n",
    "            if code[i:i+9] == \"<![CDATA[\":\n",
    "                valid = True\n",
    "                j = i + 9\n",
    "                while j < len(code) - 2:\n",
    "                    if code[j:j+3] == \"]]>\":\n",
    "                        break\n",
    "                    j += 1\n",
    "                if j >= len(code) - 2:\n",
    "                    return False\n",
    "                i = j + 3\n",
    "            elif code[i:i+2] == \"</\":\n",
    "                j = i + 2\n",
    "                while j < len(code) and code[j] != '>':\n",
    "                    if ord(code[j]) < ord('A') or ord(code[j]) > ord('Z'):\n",
    "                        return False\n",
    "                    j += 1\n",
    "                if j >= len(code) or j == i + 2 or j > i + 11:\n",
    "                    return False\n",
    "                tag = code[i+2:j]\n",
    "                if not stack or stack[-1] != tag or not tag.isupper():\n",
    "                    return False\n",
    "                stack.pop()\n",
    "                i = j + 1\n",
    "            elif code[i] == '<':\n",
    "                valid = True\n",
    "                j = i + 1\n",
    "                while j < len(code) and code[j] != '>':\n",
    "                    if ord(code[j]) < ord('A') or ord(code[j]) > ord('Z'):\n",
    "                        return False\n",
    "                    j += 1\n",
    "                if j >= len(code) or j == i + 1 or j > i + 10:\n",
    "                    return False\n",
    "                tag = code[i+1:j]\n",
    "                if not tag.isupper():\n",
    "                    return False\n",
    "                stack.append(tag)\n",
    "                i = j + 1\n",
    "            else:\n",
    "                i += 1\n",
    "        return valid and not stack\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, code: str) -> bool:\n",
    "        n = len(code)\n",
    "        tags = list()\n",
    "\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if code[i] == \"<\":\n",
    "                if i == n - 1:\n",
    "                    return False\n",
    "                if code[i + 1] == \"/\":\n",
    "                    j = code.find(\">\", i)\n",
    "                    if j == -1:\n",
    "                        return False\n",
    "                    tagname = code[i+2:j]\n",
    "                    if not tags or tags[-1] != tagname:\n",
    "                        return False\n",
    "                    tags.pop()\n",
    "                    i = j + 1\n",
    "                    if not tags and i != n:\n",
    "                        return False\n",
    "                elif code[i + 1] == \"!\":\n",
    "                    if not tags:\n",
    "                        return False\n",
    "                    cdata = code[i+2:i+9]\n",
    "                    if cdata != \"[CDATA[\":\n",
    "                        return False\n",
    "                    j = code.find(\"]]>\", i)\n",
    "                    if j == -1:\n",
    "                        return False\n",
    "                    i = j + 3\n",
    "                else:\n",
    "                    j = code.find(\">\", i)\n",
    "                    if j == -1:\n",
    "                        return False\n",
    "                    tagname = code[i+1:j]\n",
    "                    if not 1 <= len(tagname) <= 9 or not all(ch.isupper() for ch in tagname):\n",
    "                        return False\n",
    "                    tags.append(tagname)\n",
    "                    i = j + 1\n",
    "            else:\n",
    "                if not tags:\n",
    "                    return False\n",
    "                i += 1\n",
    "        \n",
    "        return not tags"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, code: str) -> bool:\n",
    "        stack = []\n",
    "        i = 0\n",
    "\n",
    "        def valid_name(name):\n",
    "            size = len(name)\n",
    "            acode, zcode = ord('A'), ord('Z')\n",
    "            if size < 1 or size > 9:\n",
    "                return False\n",
    "            for char in name:\n",
    "                if ord(char) < acode or ord(char) > zcode:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        while i < len(code):\n",
    "            if i > 0 and not stack:\n",
    "                return False\n",
    "            if code[i:i + 9] == \"<![CDATA[\":\n",
    "                j = i + 9\n",
    "                while j + 2 < len(code):\n",
    "                    if code[j: j + 3] == \"]]>\":\n",
    "                        break\n",
    "                    j += 1\n",
    "                if j + 2 >= len(code):\n",
    "                    return False\n",
    "                i = j + 3\n",
    "            elif code[i:i + 2] == \"</\":\n",
    "                j = i + 2\n",
    "                while j < len(code) and code[j] != '>':\n",
    "                    j += 1\n",
    "                if j == len(code):\n",
    "                    return False\n",
    "                temptag = code[i + 2: j]\n",
    "                if not valid_name(temptag):\n",
    "                    return False\n",
    "                if not stack or stack[-1] != temptag:\n",
    "                    return False\n",
    "                else:\n",
    "                    stack.pop()\n",
    "                i = j + 1\n",
    "            elif code[i] == \"<\":\n",
    "                j = i + 1\n",
    "                while j < len(code) and code[j] != '>':\n",
    "                    j += 1\n",
    "                if j == len(code):\n",
    "                    return False\n",
    "                temptag = code[i + 1: j]\n",
    "                if not valid_name(temptag):\n",
    "                    return False\n",
    "                stack.append(temptag)\n",
    "                i = j + 1\n",
    "            else:\n",
    "                i += 1\n",
    "        return not stack\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self,code):\n",
    "        self.s=code\n",
    "        if self.s[0]!=\"<\" or self.s[-1]!=\">\":\n",
    "            return False\n",
    "        self.skipchar()\n",
    "        name=self.expecttagname()\n",
    "        #print(name)\n",
    "        if not name:\n",
    "            return False\n",
    "        # print(name)\n",
    "        return self.completetag(name) and self.s==''\n",
    "    def expecttagname(self):\n",
    "        st=''\n",
    "        if self.s[0]=='/':\n",
    "            st+=self.s[0]\n",
    "            self.skipchar()\n",
    "        for _ in range(9):\n",
    "            if not self.s[0].isupper() and self.s[0]!='/':\n",
    "                break\n",
    "            st+=self.s[0]\n",
    "            self.skipchar()\n",
    "            if len(self.s)>0 and self.s[0]==\">\":\n",
    "                #s+=self.s[0]\n",
    "                self.skipchar()\n",
    "                #print(s)\n",
    "                return st\n",
    "\n",
    "        return ''\n",
    "    def expectcdata(self):\n",
    "        if self.s[:8]!='![CDATA[':\n",
    "            return False\n",
    "        self.s=self.s[8:]\n",
    "        while len(self.s)>=3:\n",
    "            if  self.s[:3]==']]>':\n",
    "                self.skipchar()\n",
    "                self.skipchar()\n",
    "                self.skipchar()\n",
    "                return True\n",
    "            self.skipchar()\n",
    "        return False\n",
    "\n",
    "    def skipchar(self):\n",
    "        self.s=self.s[1:]\n",
    "    def skipcon(self):\n",
    "        while self.s and self.s[0]!='<':\n",
    "            self.skipchar()\n",
    "    def completetag(self,name):\n",
    "        #n=len(name)\n",
    "        self.skipcon()\n",
    "        if not self.s:\n",
    "            return False\n",
    "        assert self.s[0]=='<'\n",
    "        self.skipchar()\n",
    "        if self.s[0]=='!':\n",
    "            #CDATA\n",
    "            #print(self.s)\n",
    "\n",
    "            if not self.expectcdata():\n",
    "                return False\n",
    "            return self.completetag(name)\n",
    "        if self.s[0]=='/':\n",
    "\n",
    "        #NAME\n",
    "            s1=self.expecttagname()\n",
    "            return s1[1:]==name\n",
    "        # elif self.s[1]!='/':\n",
    "        #     return False\n",
    "        tag=self.expecttagname()\n",
    "\n",
    "        if not tag:\n",
    "            return False\n",
    "        if not self.completetag(tag):\n",
    "            return False\n",
    "        return self.completetag(name)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, code: str) -> bool:\n",
    "        n = len(code)\n",
    "        tags = list()\n",
    "\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if code[i] == \"<\":\n",
    "                if i == n - 1:\n",
    "                    return False\n",
    "                if code[i + 1] == \"/\":\n",
    "                    j = code.find(\">\", i)\n",
    "                    if j == -1:\n",
    "                        return False\n",
    "                    tagname = code[i+2:j]\n",
    "                    if not tags or tags[-1] != tagname:\n",
    "                        return False\n",
    "                    tags.pop()\n",
    "                    i = j + 1\n",
    "                    if not tags and i != n:\n",
    "                        return False\n",
    "                elif code[i + 1] == \"!\":\n",
    "                    if not tags:\n",
    "                        return False\n",
    "                    cdata = code[i+2:i+9]\n",
    "                    if cdata != \"[CDATA[\":\n",
    "                        return False\n",
    "                    j = code.find(\"]]>\", i)\n",
    "                    if j == -1:\n",
    "                        return False\n",
    "                    i = j + 3\n",
    "                else:\n",
    "                    j = code.find(\">\", i)\n",
    "                    if j == -1:\n",
    "                        return False\n",
    "                    tagname = code[i+1:j]\n",
    "                    if not 1 <= len(tagname) <= 9 or not all(ch.isupper() for ch in tagname):\n",
    "                        return False\n",
    "                    tags.append(tagname)\n",
    "                    i = j + 1\n",
    "            else:\n",
    "                if not tags:\n",
    "                    return False\n",
    "                i += 1\n",
    "        \n",
    "        return not tags"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, code: str) -> bool:\n",
    "        self.code = code\n",
    "        if self.code[0] != '<':\n",
    "            return False\n",
    "        self.skip_one_char()\n",
    "        savt = self.expect_tag_name()\n",
    "        if not savt:\n",
    "            return False\n",
    "        return self.complete_tag(savt) and self.code == ''\n",
    "\n",
    "    def expect_tag_name(self):\n",
    "        if self.is_empty(): return ''\n",
    "        s = ''\n",
    "        for _ in range(9):\n",
    "            if self.is_empty() or self.code[0] not in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ':\n",
    "                break\n",
    "            s += self.code[0]\n",
    "            self.skip_one_char()\n",
    "        if self.is_empty(): return ''\n",
    "        if len(s) > 0 and self.code[0] == '>':\n",
    "            self.skip_one_char()\n",
    "            return s\n",
    "        return ''\n",
    "\n",
    "    def skip_one_char(self):\n",
    "        self.code = self.code[1:]\n",
    "    def complete_tag(self,savt):\n",
    "        while self.code and self.code[0] != '<':\n",
    "            self.skip_one_char()\n",
    "        if self.is_empty(): return False\n",
    "        self.skip_one_char()\n",
    "        if self.code[0] == '!':\n",
    "            if not self.expect_cdata():\n",
    "                return False\n",
    "            return self.complete_tag(savt)\n",
    "        if self.code[0] == '/':\n",
    "            self.skip_one_char()\n",
    "            return self.expect_tag_name() == savt\n",
    "        tag = self.expect_tag_name()\n",
    "        if not tag:\n",
    "            return False\n",
    "        if not self.complete_tag(tag):\n",
    "            return False\n",
    "        return self.complete_tag(savt)\n",
    "    def is_empty(self):\n",
    "        return self.code == ''\n",
    "\n",
    "    def expect_cdata(self):\n",
    "        if self.code[:8] != '![CDATA[':\n",
    "            return False\n",
    "        self.code = self.code[8:]\n",
    "        while len(self.code) >= 3:\n",
    "            if self.code[:3] == ']]>':\n",
    "                self.code = self.code[3:]\n",
    "                return True\n",
    "            self.skip_one_char()\n",
    "        return False\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
